\section{Unit 3：特征值与特征向量}

\begin{frame}{特征值问题基础}
    \begin{block}{特征值问题定义}
        对于矩阵$A \in \mathbb{C}^{n \times n}$，特征值问题：
        \[ A\mathbf{v} = \lambda \mathbf{v} \]
        \begin{itemize}
            \item $\lambda$：特征值
            \item $\mathbf{v}$：特征向量（$\mathbf{v} \neq \mathbf{0}$）
            \item 特征多项式：$\det(A - \lambda I) = 0$
        \end{itemize}
    \end{block}
    
    \begin{block}{特征值性质}
        \begin{itemize}
            \item 特征值之和等于矩阵的迹
            \item 特征值之积等于矩阵的行列式
            \item 对称矩阵的特征值都是实数
            \item 正定矩阵的特征值都是正实数
        \end{itemize}
    \end{block}
    
    \begin{exampleblock}{2×2矩阵特征值}
        \[ A = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix} \Rightarrow \lambda_1 = 5, \lambda_2 = 2 \]
    \end{exampleblock}
\end{frame}

\begin{frame}{幂法（Power Method）}
    \begin{block}{幂法基本思想}
        \begin{itemize}
            \item 寻找模最大的特征值（主特征值）
            \item 通过迭代放大主特征向量分量
            \item 适用于稀疏矩阵和大规模问题
        \end{itemize}
    \end{block}
    
    \begin{block}{幂法算法}
        \begin{enumerate}
            \item 选择初始向量$\mathbf{x}_0$（$\|\mathbf{x}_0\| = 1$）
            \item 迭代：$\mathbf{y}_k = A\mathbf{x}_{k-1}$
            \item 归一化：$\mathbf{x}_k = \mathbf{y}_k / \|\mathbf{y}_k\|$
            \item 估计特征值：$\lambda_k = \mathbf{x}_k^T A \mathbf{x}_k$
        \end{enumerate}
    \end{block}
    
    \begin{block}{收敛性分析}
        \begin{itemize}
            \item 收敛速度：$O(|\lambda_2/\lambda_1|^k)$
            \item 要求：$|\lambda_1| > |\lambda_2| \geq \cdots \geq |\lambda_n|$
            \item 初始向量不能与主特征向量正交
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{反幂法与Rayleigh商迭代}
    \begin{block}{反幂法（Inverse Power Method）}
        \begin{itemize}
            \item 寻找最接近给定$\mu$的特征值
            \item 基于$(A - \mu I)^{-1}$的幂法
            \item 收敛速度：$O(|\lambda_1 - \mu|/|\lambda_2 - \mu|)^k$
        \end{itemize}
    \end{block}
    
    \begin{block}{反幂法算法}
        \begin{enumerate}
            \item 选择位移$\mu$接近目标特征值
            \item 解线性系统：$(A - \mu I)\mathbf{y}_k = \mathbf{x}_{k-1}$
            \item 归一化：$\mathbf{x}_k = \mathbf{y}_k / \|\mathbf{y}_k\|$
            \item 估计特征值：$\lambda_k = \mathbf{x}_k^T A \mathbf{x}_k$
        \end{enumerate}
    \end{block}
    
    \begin{block}{Rayleigh商迭代}
        \begin{itemize}
            \item 反幂法的自适应版本
            \item 每次迭代更新位移$\mu_k = \mathbf{x}_k^T A \mathbf{x}_k$
            \item 具有三次收敛速度
            \item 需要解线性系统
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{QR算法}
    \begin{block}{QR算法基本思想}
        \begin{itemize}
            \item 通过QR分解迭代相似变换
            \item 将矩阵化为上三角形式（Schur形式）
            \item 适用于稠密矩阵的特征值计算
        \end{itemize}
    \end{block}
    
    \begin{block}{基本QR算法}
        \begin{enumerate}
            \item 设$A_0 = A$
            \item 对于$k = 1, 2, \ldots$
            \begin{enumerate}
                \item 计算QR分解：$A_{k-1} = Q_k R_k$
                \item 更新：$A_k = R_k Q_k$
            \end{enumerate}
            \item $A_k$收敛到上三角矩阵
        \end{enumerate}
    \end{block}
    
    \begin{block}{收敛性}
        \begin{itemize}
            \item 对角元素收敛到特征值
            \item 收敛速度取决于特征值分离程度
            \item 实际使用带位移的QR算法
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{对称矩阵的特征结构}
    \begin{block}{对称矩阵性质}
        \begin{itemize}
            \item 所有特征值都是实数
            \item 特征向量可以选为正交的
            \item 可对角化：$A = Q\Lambda Q^T$
            \item 谱定理：存在正交基使$A$对角化
        \end{itemize}
    \end{block}
    
    \begin{block}{对称矩阵特征值算法}
        \begin{itemize}
            \item Lanczos算法：适用于大型稀疏矩阵
            \item 分治法：适用于三对角矩阵
            \item Jacobi方法：通过Givens旋转对角化
            \item QR算法：适用于稠密对称矩阵
        \end{itemize}
    \end{block}
    
    \begin{block}{特征值分布}
        \begin{itemize}
            \item Courant-Fischer定理：特征值的极小极大刻画
            \item Weyl定理：特征值扰动分析
            \item 特征值包含定理：Gershgorin圆盘
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{应用：图拉普拉斯与马尔科夫链}
    \begin{block}{图拉普拉斯矩阵}
        对于无向图$G = (V, E)$：
        \[ L = D - A \]
        \begin{itemize}
            \item $D$：度矩阵（对角）
            \item $A$：邻接矩阵
            \item 特征值反映图的结构性质
        \end{itemize}
    \end{block}
    
    \begin{block}{拉普拉斯特征值性质}
        \begin{itemize}
            \item 特征值非负：$0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$
            \item $\lambda_2$：代数连通度（图连通性度量）
            \item 特征向量：图的谱嵌入
        \end{itemize}
    \end{block}
    
    \begin{block}{马尔科夫链}
        \begin{itemize}
            \item 转移矩阵$P$：行和为1的非负矩阵
            \item 主特征值：$\lambda_1 = 1$
            \item 平稳分布：主左特征向量
            \item 收敛速度：由次大特征值模决定
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{应用：PageRank算法}
    \begin{block}{PageRank基本思想}
        \begin{itemize}
            \item 网页重要性排序算法
            \item 基于随机游走模型
            \item 网页的PageRank值是其平稳分布概率
        \end{itemize}
    \end{block}
    
    \begin{block}{PageRank矩阵}
        \[ P = \alpha M + (1-\alpha)\mathbf{v}\mathbf{e}^T \]
        \begin{itemize}
            \item $M$：归一化链接矩阵
            \item $\alpha$：阻尼因子（通常0.85）
            \item $\mathbf{v}$：个性化向量
            \item $\mathbf{e}$：全1向量
        \end{itemize}
    \end{block}
    
    \begin{block}{PageRank计算}
        \begin{itemize}
            \item 幂法：$\mathbf{x}_{k+1} = P\mathbf{x}_k$
            \item 快速收敛：$O(\alpha^k)$
            \item 适用于超大规模稀疏矩阵
            \item 实际使用：$\mathbf{x}_{k+1} = \alpha M\mathbf{x}_k + (1-\alpha)\mathbf{v}$
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{特征值算法比较}
    \begin{block}{算法选择指南}
        \begin{itemize}
            \item \textbf{幂法}：主特征值，稀疏大矩阵
            \item \textbf{反幂法}：特定特征值，已知近似值
            \item \textbf{QR算法}：所有特征值，稠密中小矩阵
            \item \textbf{Lanczos算法}：部分特征值，大型稀疏对称矩阵
            \item \textbf{Jacobi方法}：所有特征值，对称矩阵
        \end{itemize}
    \end{block}
    
    \begin{block}{计算复杂度}
        \begin{itemize}
            \item 幂法：每次迭代$O(n^2)$，收敛线性
            \item QR算法：$O(n^3)$，收敛二次
            \item Lanczos：$O(n^2)$每次迭代，收敛超线性
            \item 分治法：$O(n^2)$，三对角对称矩阵
        \end{itemize}
    \end{block}
    
    \begin{block}{数值稳定性}
        \begin{itemize}
            \item QR算法：向后稳定
            \item Lanczos算法：可能丢失正交性
            \item 幂法：对初始向量敏感
            \item 需要重新正交化技术
        \end{itemize}
    \end{block}
\end{frame}

\begin{frame}{本章重点总结}
    \begin{block}{核心算法}
        \begin{itemize}
            \item 幂法与反幂法
            \item Rayleigh商迭代
            \item QR算法
            \item 对称矩阵特征值算法
        \end{itemize}
    \end{block}
    
    \begin{block}{重要应用}
        \begin{itemize}
            \item 图拉普拉斯特征值分析
            \item 马尔科夫链平稳分布
            \item PageRank网页排序
            \item 谱图理论与聚类
        \end{itemize}
    \end{block}
    
    \begin{block}{学习目标}
        \begin{itemize}
            \item 掌握特征值问题的数值解法
            \item 理解不同算法的适用场景
            \item 能够分析算法收敛性和稳定性
            \item 应用特征值计算解决实际问题
        \end{itemize}
    \end{block}
\end{frame}